package dynamicProgramming.review11_15;

//TODO:2023/11/15 最长公共子序列
public class Class1143 {
//TODO:2023/11/15  dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp=new int[m+1][n+1];
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
 int ans=0;
        for (int i = 1; i <=m; i++) {
            for (int j = 1; j <=n; j++) {
                if (chars1[i-1]==chars2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    //TODO:2023/11/15 这里是求取最长的公共序列  取两者的最大数值
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
                ans=Math.max(dp[i][j],ans);

            }
        }
        return  ans;

    }

}
